package simple.tree;

import struct.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/range-sum-of-bst/">938. 二叉搜索树的范围和</a>
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * 示例 1：
 *   输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
 *   输出：32
 * 示例 2：
 *   输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
 *   输出：23
 * 提示：
 *   树中节点数目在范围 [1, 2 * 10^4] 内
 *   1 <= Node.val <= 10^5
 *   1 <= low <= high <= 10^5
 * @author 刘学松
 * @date 2023-06-30 14:50
 */
public class 二叉搜索树的范围和 {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        if (low <= root.val && root.val <= high) {
            sum += root.val;
            if (root.left != null) {
                sum += rangeSumBST(root.left, low, high);
            }
            if (root.right != null) {
                sum += rangeSumBST(root.right, low, high);
            }
        } else if (root.val < low) {
            if (root.right != null) {
                sum += rangeSumBST(root.right, low, high);
            }
        } else {
            if (root.left != null) {
                sum += rangeSumBST(root.left, low, high);
            }
        }
        return sum;
    }
}
